package com.cat.binaryTree;

import java.net.Inet4Address;
import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-binary-tree-ii/
 * @create 2025/9/16 09:29
 * @since JDK17
 */

public class Solution53 {
    List<Integer> list = new ArrayList<>();
    void f(TreeNode root) {
        if (root == null) {
            return;
        }
        f(root.left);
        list.add(root.val);
        f(root.right);
    }

    TreeNode f2(int l, int r) {
        if (l > r) {
            return null;
        }
        int max = l;
        for (int i = l + 1; i <= r; i++) {  // 找到最大值
            if (list.get(max) < list.get(i)) {
                max = i;
            }
        }
        return new TreeNode(list.get(max), f2(l, max - 1), f2(max + 1, r));
    }
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        f(root);
        list.add(val);
        return f2(0, list.size() - 1);
    }
}
